1305D - Kuroni and the Celebration - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll INF=1e18;
const int M=998244353;
const int N=1e3+100;
vector<set<int>>adj;
set<int>prs;
vector<int>par;
int n;
int inv(int i){
  return i <= 1 ? i : M - (long long)(M/i) * inv(M % i) % M;
}
int binpow(int a,int p){
  int ans=1;
  while(p>0){
    if(p%2){
      ans=(ans*a);
    }
    a=(a*a);
    p/=2;
  }
  return ans;
}
void dfs(int s,vector<int>&d,vector<int>&v){
  v[s]=1;
  for(auto it:adj[s]){
    if(v[it]==0&&prs.find(it)!=prs.end()){
      d[it]=d[s]+1;
      par[it]=s;
      dfs(it,d,v);
    }
  }
}
vector<int>diameter(int s){
  vector<int>vis,dis;
  dis.assign(n,INF);
  vis.assign(n,0);
  dis[s]=0;
  dfs(s,dis,vis);
  int ma=s;
  int c=0;
  for(int i=0;i<n;i++){
    if(dis[i]==INF)continue;
    if(dis[ma]<dis[i])ma=i;
    c++;
    //cout<<i+1<<" ";
  }
  
  dis.assign(n,INF);
  vis.assign(n,0);
  dis[ma]=0;par[ma]=ma;
  dfs(ma,dis,vis);
  int ma2=s;
  for(int i=0;i<n;i++){
    if(dis[i]==INF)continue;
    if(dis[ma2]<dis[i])ma2=i;
  }
  
  vector<int>ans={dis[ma2],ma,ma2,c};
  return ans;
}
int32_t main(){
  IOS
  int t=1;
  //cin>>t;
  while(t--){
    cin>>n;
    adj.assign(n,{});
    par.assign(n,-1);
    prs.insert(n-1);
    for(int i=0;i<n-1;i++){
      prs.insert(i);
      int a,b;
      cin>>a>>b;
      a--;b--;
      adj[b].insert(a);
      adj[a].insert(b);
    }
    int cur=n;
    int pnode=0;
    int lca=0;
    if(n==2){
      cout<<"? "<<1<<" "<<2<<endl;
      cin>>lca;
      cout<<"! "<<lca<<endl;
      continue;
    }
    vector<int>d=diameter(pnode);
    int c=0;
    while(prs.size()>3){
      if(c==(n/2)){
        cout<<-1<<endl;
        return 0;
      }
      cout<<"? "<<d[1]+1<<" "<<d[2]+1<<endl;
      c++;
      cin>>lca;
      lca--;
      pnode=lca;
      if(lca==d[1]||lca==d[2]){
        cout<<"! "<<lca+1<<endl;
        return 0;
      }
      prs.erase(d[1]);
      prs.erase(d[2]);
      d=diameter(lca);
    }
    cout<<"! "<<lca+1<<endl;
    cout.flush();
  }
  return 0;
}